//树的层序遍历相当于广度优先搜索。
//使用一个队列进行辅助，每次访问结点时，将其左右孩子入队，每一个完整for循环访问一层
#include <vector>
#include <queue>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
};

vector<vector<int>> levelOrder(TreeNode* root)
{
    queue<TreeNode*> que;
    vector<vector<int>> result;
    if(root) que.push(root);
    while(!que.empty()) //队列空则全部访问完毕
    {
        vector<int> vec;
        TreeNode* node;
        int size=que.size();//每层循环用的是一个size，但总的que长度会变，所以用一个size记录当前要遍历的结点
        for(int i=0;i<size;i++)
        {
            node=que.front();
            que.pop();
            vec.push_back(node->val);
            if(node->left) que.push(node->left);    //左子树入队
            if(node->right) que.push(node->right);  //右子树入队
        }
        //一层遍历完成
        result.push_back(vec);
    }

    return result;
    
}